// https://leetcode.cn/problems/unique-paths-iii/

// 题干：在二维网格 grid 上，有 4 种类型的方格：
//      1 表示起始方格。且只有一个起始方格。
//      2 表示结束方格，且只有一个结束方格。
//      0 表示我们可以走过的空方格。
//      -1 表示我们无法跨越的障碍。
//      返回在四个方向（上、下、左、右）上行走时，从起始方格到结束方格的不同路径的数目。
//      每一个无障碍方格都要通过一次，但是一条路径中不能重复通过同一个方格。

// 示例：输入：[[1,0,0,0],[0,0,0,0],[0,0,2,-1]]
//      输出：2

// 碎语：先扫描数组，得到起始位置，在走到结束位置前不判断路径合不合法
//       到达结束位置后再判断，通过0的个数来判断合不合法

#include <bits/stdc++.h>
using namespace std;

class Solution
{
    int m, n, ret;
    int sumZeros;
    bool vis[21][21];
public:
    int uniquePathsIII(vector<vector<int>>& grid)
    {
        ret = 0, sumZeros = 0;
        m = grid.size(), n = grid[0].size();
        memset(vis, 0, sizeof(vis));

        for (int i = 0 ; i < m ; i++){
            for (int j = 0 ; j < n ; j++){
                if (!grid[i][j]) sumZeros++;
            }
        }

        for (int i = 0 ; i < m ; i++){
            for (int j = 0 ; j < n ; j++){
                if (grid[i][j] == 1){
                    vis[i][j] = true;
                    dfs(grid, i, j, 0);
                }
            }
        }

        return ret;
    }

    int dx[4] = {-1,1,0,0};
    int dy[4] = {0,0,-1,1};

    void dfs(vector<vector<int>>& grid, int i, int j, int countZeros)
    {
        if (grid[i][j] == 2){
            if (countZeros == sumZeros) ret++;
            return ;
        }

        for (int k = 0 ; k < 4 ; k++){
            int x = i + dx[k], y = j + dy[k];

            if (x >= 0 && x < m && y >= 0 && y < n && (!grid[x][y] || grid[x][y] == 2) && !vis[x][y]){
                vis[x][y] = true;
                if (!grid[x][y]) countZeros++;
                dfs(grid, x, y, countZeros);

                vis[x][y] = false;
                if (!grid[x][y]) countZeros--;
            }

        }
    }
};

int main()
{
    Solution sol;
    vector<vector<int>> grid = {{1,0,0,0},{0,0,0,0},{0,0,2,-1}};

    cout << sol.uniquePathsIII(grid) << endl;

    return 0;
}